

#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;

class Solution
{
    vector<int> vis;
    vector<int> path;
    vector<vector<int>> res;
    using USI = unordered_set<int>;

public:
    vector<vector<int>> permute1(vector<int>& nums)
    {
        if (1 == nums.size())
            return { {nums} };

        res.reserve(720 * 6);
        _permute1(nums, 0);

        return res;
    }

    vector<vector<int>> permute2(vector<int>& nums)
    {
        if (1 == nums.size())
            return { {nums} };

        path.reserve(6);
        vis.resize(6);
        res.reserve(720 * 6);
        _permute2(nums, 0);

        return res;
    }

    int totalNQueens1(int n)
    {
        if (1 == n)
            return 1;
        if (n < 4)
            return 0;

        int res = 0;

        _totalNQueens1(res, 0, n, 0, 0, 0);

        return res;
    }

    int totalNQueens2(int n)
    {
        if (1 == n)
            return 1;
        if (n < 4)
            return 0;

        USI cols, diags1, diags2;

        return _totalNQueens2(n, 0, cols, diags1, diags2);
    }

private:
    void _totalNQueens1(int& res, int row, int n, int cols, int mainDiagonals, int secondaryDiagonals)
    {
        if (row == n)
        {
            ++res;
            return;
        }

        int tries = ~(cols | mainDiagonals | secondaryDiagonals) & ((1 << n) - 1);

        for (int atry = 0; tries; tries &= tries - 1)
        {
            atry = -tries & tries;
            _totalNQueens1(res, row + 1, n, cols | atry, (mainDiagonals | atry) << 1, (secondaryDiagonals | atry) >> 1);
        }
    }

    int _totalNQueens2(int n, int row, USI& cols, USI& diags1, USI& diags2)
    {
        if (row == n)
            return 1;

        int cnt = 0;

        for (int col = 0; col < n; ++col)
        {
            int pos1 = row - col;
            int pos2 = row + col;

            if (cols.find(col) != cols.end()
                || diags1.find(pos1) != diags1.end()
                || diags2.find(pos2) != diags2.end())
                continue;

            cols.insert(col);
            diags1.insert(pos1);
            diags2.insert(pos2);
            cnt += _totalNQueens2(n, row + 1, cols, diags1, diags2);

            cols.erase(col);
            diags1.erase(pos1);
            diags2.erase(pos2);
        }

        return cnt;
    }

    void _permute1(vector<int>& nums, int index)
    {
        if (index == nums.size())
        {
            res.push_back(nums);
            return;
        }

        for (int i = index; i < nums.size(); ++i)
        {
            swap(nums[index], nums[i]);
            _permute1(nums, index + 1);
            swap(nums[index], nums[i]);
        }
    }

    void _permute2(vector<int>& nums, int index)
    {
        if (index == nums.size())
        {
            res.push_back(path);
            return;
        }

        for (int i = 0; i < nums.size(); ++i)
        {
            if (!vis[i])
            {
                vis[i] = 1;
                path.push_back(nums[i]);
                _permute2(nums, index + 1);
                path.pop_back();
                vis[i] = 0;
            }
        }
    }
};

void Test1()
{

}

int main()
{
    Test1();

	return 0;
}